import numpy as np
import scipy.sparse as spm


def checkendsjunctions(area,val4one):
    """
    功能：检查8-连通区域中心是一个交叉点(1)，还是端点(2)，还是普通边像素(0)
    area是一个3x3二值化图像区域
    val4one为二值化图像中1对应的实际值
    """
    x=area.reshape(9,order=2);  #按第二个维度（列）
    """
    0,3,6
    1,4,7  ==> (0,1,2,3,4,5,6,7,8)'
    2,5,8
    """
    a=np.array([x[0],x[1],x[2],x[5],x[8],x[7],x[6],x[3]],np.int8)   #防止转化为uint8
    b=np.array([x[1],x[2],x[5],x[8],x[7],x[6],x[3],x[0]],np.int8)
    crossings=np.sum(np.abs(a-b))
    if val4one==x[4] and crossings>=6*val4one:
        return 1    #junction
    elif val4one==x[4] and crossings == 2*val4one:
        return 2    #ending
    else:
        return  0

def findendsjunctions(bin,val4one):
    """
    功能：在边图像中查找端点和交叉点
    输出：端点列表和交叉点坐标元组的列表 [(y1,x1),(y2,x2),.....]
    输入：bin为二值化图像,使用canny处理的图像在最外一圈像素值都是0
            val4one为二值化图像中1对应的实际值
    """
    nHeight, nWidth = bin.shape[:2]
    jlist=[]
    elist=[]
    for c in range(1,nWidth-1):    #rows,y轴
        for r in range(1,nHeight-1): #columns,x轴
            ret=checkendsjunctions(bin[r-1:r+2,c-1:c+2],val4one)
            if ret==1:    #junction
                jlist.append((r,c))
            elif ret==2:    #ending
                elist.append((r,c))

    return elist,jlist

def availablepixels(px,edgeNo,edgeImg,JUNCT):
    """
    功能：返回指定像素px的8-邻域内的有效像素。有效的定义：未标记的边像素，不是指定编号edgeNo的交叉点
    edgeNo: =0表示允许返回所有的交叉点
    edgeImg:边的图像
    jlist: 交叉点列表
    """
    neighbor=np.array([[-1,-1],[-1,0],[-1,1],[1,-1],[1,0],[1,1],[0,-1],[0,1]])
    neighbor=neighbor+[px[0],px[1]]
    palist=[]
    pjlist=[]
    for px in neighbor:
        if edgeImg[px[0],px[1]] == 1 and \
                JUNCT[px[0],px[1]] ==0 :  #像素是未标记边像素，且不是边的交叉点
            palist.append((px[0],px[1]))
        elif edgeImg[px[0],px[1]] != -edgeNo and JUNCT[px[0],px[1]]!=0:
            pjlist.append((px[0],px[1]))
    return palist,pjlist

def trackedges(edgeImg,startPx,nextPx,edgeNo,JUNCT,avoidJunction):
    """
    edgeImg: 边图
    startPx: 起始点，端点或交叉点
    edgeNo: 指定的边的编号
    avoidJunction: True表示避开交叉点，而只以端点终止
    """
    edgepts=[]; edgepts.append(startPx)
    preferredDir=False
    edgeImg[startPx[0],startPx[1]] = -edgeNo
    #如果指定nextPx，则从这个方向开始追踪
    if ((type(nextPx)==tuple) or type(nextPx)==list) and len(nextPx)>=2:
        curPx=nextPx
        edgepts.append(nextPx)
        edgeImg[nextPx[0],nextPx[1]]=-edgeNo
        preferredDir=True
        dirn=np.array(nextPx)-np.array(startPx)   #单位化
        dirn=dirn/np.sum(dirn**2)**0.5
    else:
        curPx=startPx
        dirn=[0,0]
    #找到当前点8连通邻域内的其它有效点
    aelist,ajlist=availablepixels(curPx,edgeNo,edgeImg,JUNCT)
    while len(aelist)!=0 or len(ajlist)!=0:
        #首先看是否能链接到一个交叉点。选择的交叉点产生一个移动。
        if len(ajlist)!=0 and ((not avoidJunction) or len(aelist)==0):
            #如果有偏好的方向，则移动尽可能的接近指定方向
            if preferredDir:
                dotp=-np.inf
                #在当前位置邻域内的有效交叉点上循环
                #找到与指定方向最接近的方向
                for jj in ajlist:
                    dirna = np.array(jj)-np.array(curPx)   #计算交叉点相对当前位置的方向
                    dirna =dirna/np.sum(dirna**2)**0.5   #方向向量单位化
                    dp=np.dot(dirn,dirna)   #取与指定方向的夹角
                    if dp>dotp:
                        dotp=dp;
                        pxbest=jj
                        dirnbest=dirna
            #否则，应该尽可能选择一个4连通的交叉点
            else:
                distbest=np.inf
                #在当前位置邻域内的有效边像素上循坏
                #找到与当前位置最近的交叉点（尽可能四连通邻域像素）
                for jj in ajlist:
                    dist=np.sum(np.array(jj)-np.array(curPx))
                    if dist <distbest:
                        pxbest=jj
                        distbest=dist;
                        dirnbest= np.array(jj)-np.array(curPx)
                        dirnbest = np.sum(dirnbest**2)**0.5
                preferredDir=True
        #没有有效的交叉点,那么选择一个有效的边像素点做为前进方向
        else:
            dotp=-np.inf;
            for en in aelist:
                dirna = np.array(en)-np.array(curPx)
                dirna=dirna/ np.sum(dirna**2)**0.5    #计算像素点相对中心的方向，并单位化
                dp=np.dot(dirn,dirna)
                if dp>dotp:
                    pxbest=en
                    dirnbest=dirna
            #如果设置了avoidJunction,则清除之
            avoidJunction=0
        #添加最新选择的前进点到边像素列表中
        curPx=pxbest
        dirn=dirnbest
        edgepts.append(curPx)
        edgeImg[curPx[0],curPx[1]]=-edgeNo
        #edgeImg[pxbest[0],pxbest[1]]=-edgeNo    #为新当前点赋予边编号
        #如果当前点为交叉点，那么返回
        if JUNCT[curPx[0],curPx[1]]!=0:
            return edgepts,1
        else: #当前点为非交叉点，继续追踪,获取当前点的邻域有效像素
            aelist,ajlist=availablepixels(curPx,edgeNo,edgeImg,JUNCT)
    #end of while
    #如果执行到下面的代码，说明达到了另一个端点.
    #这里存在一个loop的判断问题，条件如下：
    #1，且loop最少由4个像素组成。
    #2，两个端点相互间差一个像素。
    if len(edgepts)>=4:
        ep1=edgepts[0]
        ep2=edgepts[-1]
        if np.abs(ep1[0]-ep2[0]) <=1 and np.abs(ep1[1]-ep2[1]) <=1:
            edgepts.append(ep1)
            return edgepts,5
        return edgepts,0

def edgelink(binImg, minlength=1):
    """
    bin:输入二值化边图像
    minlength:指定感兴趣边的最小长度，默认为1
    返回：边列表，边类型。
    边类型：
        0  - Start free, end free
        1  - Start free, end junction
        2  - Start junction, end free (should not happen)
        3  - Start junction, end junction
        4  - Loop
    """
    #删除图像中的孤点(???)

    #寻打图像中的端点和交叉点，返回各自像素点的列表
    elist,jlist=findendsjunctions(binImg,1)
    Njunct=len(jlist)
    Nends=len(elist)

    #为交叉点创建稀疏矩阵
    JUNCT=spm.lil_matrix(np.zeros(binImg.shape[:2]))
    for jn in jlist:
        JUNCT[jn[0],jn[1]]=1

    ##step 1 对每一个未标记的端点进行边追踪，直到遇到另一个端点或交叉点
    edgeNo=0
    edgeList=[]
    endTypeList=[]
    for en in elist:
        if binImg[en[0],en[1]] ==1:  #1表示未标记的边像素
            edgeNo=edgeNo+1
            edgePts,endType=trackedges(binImg,en,[],edgeNo,JUNCT,False)
            edgeList.append(edgePts)
            endTypeList.append(endType)

    ##step 2 处理交叉点
    for jj in jlist:
        if JUNCT[jj[0],jj[1]] !=2:    #此交叉点还没有访问过
            JUNCT[jj[0],jj[1]] =2
            #使用edgeNo=0调用availablepixels，得到该交叉点邻域内所有交叉点以及未标记边像素
            aelist,ajlist=availablepixels(jj,0,binImg,JUNCT)
            #1,对于邻近交叉点，若其也未被仿问则将它们成对添加到edgeList
            for jk in ajlist:
                edgeNo=edgeNo+1
                binImg[jj[0],jj[1]]=-edgeNo
                binImg[jk[0],jk[1]]=-edgeNo
                edgePts=[]; edgePts.append(jj); edgePts.append(jk)
                edgeList.append(edgePts)
                endTypeList.append(3)
                #检查交叉点jpx与邻近交叉点jpxx有共同的未追踪的像素
                aelistk,dummy=availablepixels(jk,0,binImg,JUNCT)
                #如果两个交叉点都有未追踪像素，则需要检查是否是共同的
                if len(aelist)!=0 and len(aelistk)!=0:
                    #查找两个列表是否有相同的
                    commonrc=set(aelistk) & set(aelist)
                    for px in commonrc:
                        #以更接近（距离更近）交叉点为起点执行边追踪
                        distj=np.sum((np.array(px)-np.array(jj))**2)
                        distk=np.sum((np.array(px)-np.array(jk))**2)
                        edgeNo=edgeNo+1;
                        if distj<distk:
                            edgePts,endType =trackedges(binImg,jj,px,edgeNo,JUNCT,False)
                        else:
                            edgePts,endType =trackedges(binImg,jk,px,edgeNo,JUNCT,False)
                        edgeList.append(edgePts)
                        endTypeList.append(3)  #边类型是junction to junction
                #2,对于未标记的边像素，则对其进行追踪
                for em in aelistk:
                    if binImg[em[0],em[1]] == 1:
                        edgeNo=edgeNo+1;
                        #以交叉点为起点，apxx为下一点进行边追踪
                        edgePts,endType=trackedges(binImg,jk,em,edgeNo,JUNCT,False)
                        edgeList.append(edgePts)
                        endTypeList.append(3)   #边类型是junction to junction
                ##将这个邻近交叉点标记为2，表示已经处理了
                JUNCT[jk[0],jk[1]]=2
            #end of all adjacent junctions
            for em in aelist:
                if binImg[em[0],em[1]] ==1:
                    edgeNo=edgeNo+1
                    edgePts,endType=trackedges(binImg,jj,em,edgeNo,JUNCT,False)
                    edgeList.append(edgePts)
                    endTypeList.append(3) #边类型是junction to junction
     #end of each junction

    #step 3 扫描图像，寻找剩余未标记像素。它们应该是单独的loop
    nHeight, nWidth = binImg.shape[:2]
    for r in range(1,nHeight-1):    #rows,y轴
        for c in range(1,nWidth-1): #columns,x轴
            if binImg[r,c]==1:
                edgeNo = edgeNo+1
                edgePts,endType=trackedges(binImg,binImg[r,c],[],edgeNo,JUNCT,False)
                edgeList.append(edgePts)
                endTypeList.append(endType)

    return edgeList,endTypeList


"""
##canny参数
fileName=r'misc_pic\B.png'
high_threshold =80
low_threshold=30

##载入图像
img = cv2.imread(fileName)
img= cv2.cvtColor(img,cv2.COLOR_RGB2GRAY)
##进行canny边缘检测
edge=canny.canny_edge_detector(img,high_threshold,low_threshold)

plt.gray()
plt.imshow(edge,interpolation="nearest")
plt.show()

##查找交叉点和端点
elist,jlist=findendsjunctions(edge,1)

x=checkendsjunctions(np.array([[255,0,0],[0,255,0],[0,0,0]]), 255)
print(x)
"""

"""
###edgelink函数测试
testImage=np.array([[0,0,0,0,0,0,0,0],
                    [0,1,0,0,0,1,0,0],
                    [0,0,1,0,1,0,1,0],
                    [0,0,1,0,0,1,0,0],
                    [0,0,0,1,1,1,1,0],
                    [0,0,0,1,0,0,1,0],
                    [0,0,1,1,1,1,0,0],
                    [0,0,0,0,0,0,0,0] ])

testImage=bwmorph_thin.bwmorph_thin(testImage)
print(testImage)

edgeList,endTypeList=edgelink(testImage)

for edge in edgeList:
    print(edge)

for type in endTypeList:
    print(type)

print(testImage)
"""
